Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs

摘要

Pebble games are single-player games on DAGs involving placing and movingpebbles on nodes of the graph according to a certain set of rules. The goal isto pebble a set of target nodes using a minimum number of pebbles. In thispaper, we present a possibly simpler proof of the result in [CLNV15] andstrengthen the result to show that it is PSPACE-hard to determine the minimumnumber of pebbles to an additive $n^{1/3-\epsilon}$ term for all $\epsilon >0$, which improves upon the currently known additive constant hardness ofapproximation [CLNV15] in the standard pebble game. We also introduce a familyof explicit, constant indegree graphs with $n$ nodes where there exists a graphin the family such that using constant $k$ pebbles requires $\Omega(n^k)$ movesto pebble in both the standard and black-white pebble games. This independentlyanswers an open question summarized in [Nor15] of whether a family of DAGsexists that meets the upper bound of $O(n^k)$ moves using constant $k$ pebbleswith a different construction than that presented in [AdRNV17].